package TestHeap;

import javax.swing.tree.TreeNode;
import java.util.Arrays;

public class Heap {
    public int[] elem;
    public int usedsize;

    public Heap(int n)
    {
        elem = new int[n];
    }

    //插入元素
    public void initElem(int[] array)
    {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedsize++;
        }
    }
    //创建大根堆
    public void createBigHeap()
    {
        for (int parent = (usedsize-1-1)/2; parent >=0 ; parent--) {
            siftdown(parent, usedsize);
        }
    }


    public void createLittleHeap()
    {

        for (int parent = (usedsize-1-1)/2 ; parent >=0 ; parent--) {

                    Siftdown(parent,usedsize);
        }
    }

    //向下调整
    private void siftdown(int parent, int end)
    {
            int child = 2*parent+1;
       while(child<end)
       {
           if(elem[child]< elem[child+1] && child+1 < usedsize)     //确保右子树一定存在再进行比较，child一定是左右孩子结点的较大者
           {
               child++;
           }
           if(elem[child] > elem[parent])
           {
               Swap(child,parent);
               parent = child;                  //交换完之后再向下调整
               child = 2*parent+1;
           }
           else {
               break;
           }
       }
    }
    private void Siftdown(int parent, int end)
    {
        int child = 2*parent+1;
        while(child<end)
        {
            if(child+1 < usedsize && elem[child]>elem[child+1]  )     //确保右子树一定存在再进行比较
            {
                child++;
            }
            if(elem[child] < elem[parent])
            {
                Swap(child,parent);
                parent = child;                  //交换完之后再向下调整
                child = 2*parent+1;
            }
            else {
                break;
            }
        }
    }

    //向上调整(大根堆模式)
    public void siftup(int child)
    {
        int parent = (child-1)/2;
        while(child > 0) {
            if(elem[child]>elem[parent])
            {
                Swap(child,parent);
                child = parent;
                parent =(child-1)/2;
            }
            else {
                break;
            }
        }
    }
    //交换
    public void Swap(int i,int j)
    {
        int tmp;
        tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    public Boolean isfull()
    {
        return usedsize == elem.length;
    }
    //插入
    public void offer(int val)
    {
        //判断是否需要扩容
        if(isfull())
        {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        //插入元素
        elem[usedsize] = val;
        usedsize++;
        siftup(usedsize-1);
    }
    //删除
    public int poll()
    {
        int tmp = elem[0];
        Swap(0,usedsize-1);
        usedsize--;
        siftdown(0,usedsize);
        return tmp;
    }
    public static void main(String[] args) {
        int[] array = {77,13,46,20,28,37,55,19,9};
        Heap heap = new Heap(9);
        heap.initElem(array);
    /*    heap.offer(50);
        heap.poll();*/
        heap.createLittleHeap();
    //    heap.createBigHeap();*/
        System.out.println("=============================");
    }
}
